# 《Redis 设计与实现》笔记之字典

# 一、字典的定义

字典是一个保存键值对的抽象数据类型。

Redis 使用的 C 语言没有这种数据结构，因此 Redis 构建了自己的字典实现。

Redis 数据库就是使用字典作为底层实现，增删改查的操作都是对字典操作。

# 二、字典的实现

Redis 字典使用哈希表来实现，一个哈希表里面可以有多个哈希表节点，每一个哈希表节点是一个键值对。

# 2.1 哈希表

typedef struct dictht {
    // 哈希表数组
    dictEntry **table;

    // 哈希表大小
    unsigned long size;

    // 哈希表大小掩码，总是为 size - 1
    unsigned long sizemask;

    // 该哈希表目前有的哈希表节点数量
    unsigned long used;
};

1
2
3
4
5
6
7
8
9
10
11
12
13

**table** 是一个数组，数组中的每一个元素都是 dictEntry类型的哈希表节点。
**sizemask**属性决定一个键应该放在哪个位置。

# 2.2 哈希表节点

typedef struct dictEntry {
    // 哈希表节点的键
    void *key;

    // 哈希表节点的值
    union {
        void *val;
        uint64_t u64;
        int64_t s64;
        double d;
    } v;

    // 形成链表
    struct dictEntry *next;     /* Next entry in the same hash bucket. */
} dictEntry;

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

键值对的值可以是一个 void *指针，uint64_t 整数，或者 int64_t 整数。 next 指向另一个哈希表节点，通过它可以避免键冲突，即两个键映射到同一个位置的问题。

# 2.3 字典

typedef struct dict {
    // 类型特定函数
    dictType *type;

    // 私有数据
    void *privdata;

    // 哈希表数组
    dictht ht[2];

    // rehash 索引
    int trehashidx;

} dict;

1
2
3
4
5
6
7
8
9
10
11
12
13
14

**type** 属性执行一个 dictType结构的指针，dictType中保存着一些类型特定函数，Redis 会为不同的类型设置不同的函数。
**privdata** 是类型特定函数的参数

typedef struct dictType {
    // 计算哈希值
    unsigned int (*hashFunction)(const void *key);

    // 复制键
    void *(*keyDup)(void *privdata, const void *key);

    // 复制值
    void *(*valDup)(void *privdata, const void *obj);

    // 比较键
    int (*keyCompare)(void *privdata, const void *key1, const void *key2);

    // 销毁键
    void (*keyDestructor)(void *privdata, void *key);

    // 销毁值
    void (*valDestructor)(void *privdata, void *obj);
} dictType;

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19

**ht** 属性是一个哈希表数组，数组有两个元素，每一个元素是一个哈希表。正常情况只使用 ht[0]，只有对 ht[0] 进行 rehash 时候，ht[1] 才使用。
rehashidx属性记录 rehash 目前的进度，没有在进行 rehash 时，值为 -1。

# 三、哈希算法

把一个键值对添加到字典中的时候，通过键计算出哈希值和**索引值，**然后根据索引值，将哈希表节点放在这个索引下。

计算键的 hash 值

hash = dict->type->hashFunction(key)

计算索引值

index = hash & dict->ht[x].sizemask; // x 为 0 或 1，看情况

字典作为数据库或者哈希表的底层实现时，哈希算法是 MurmurHash 算法。

MurmurHash 算法的优点在于对于规律性很强的键，它的随机分布特征表现得也很好。

# 四、解决键冲突

第一个键值对被分配到 5 这个索引上，第二个键值对也分配到 5 这个索引上，我们称之为键发生冲突。

Redis 使用链地址法来解决键冲突，每一个哈希表节点都有一个 next指针，如果发生键冲突，那么可以用 next指针指向新的键值对，构成链表，这就解决了键冲突的问题。

# 五、rehash 重新散列

当哈希表的键值对太多或者太少的时候，我们需要对它的大小进行收缩或者扩展，这个操作通过 rehash 重新散列来完成。

# 5.1 rehash 步骤

为哈希表 ht[1] 分配空间，如果执行扩展，那么 ht[1] 的大小是第一个大于等于 ht[0].used，即如果 ht[0].used

# 六、渐进式 rehash

扩展或收缩的时候需要将 ht[0] 中的键值对移到 ht[1]，这个过程不是一次性的，而是多次，漫漫地，渐进式地完成。

因为如果 ht[0] 保存着几百万、几千万个键值对，一次性移动的话，会导致服务器停止一段时间，用户体验就很差了。

渐进式 rehash 步骤：

为 ht[1] 分配空间
设一个变量 rehashidx，将其初始化为 0，表示 rehash 工作开始。

添加的时候，全部添加到 ht[1] 中，确保 ht[0] 中的键值对只减不增。

# 参考资料

Murmur 哈希

← 《Redis 设计与实现》笔记之链表